#include <gmock/gmock.h>
#include <map>
#include <vector>
#include <math.h>
#include <algorithm>
//#include <ctime>
#include <stdio.h>

#include "DMMath.hpp"

using namespace KDM::math;


class DMMathTest : public ::testing::Test
{
protected:
	typedef int Integer;

	DMMathTest() : _sizeArray(10000), _countIterations(100), _data(_sizeArray), _rnd(0, _sizeArray - 1), _dataPointers(_sizeArray),
		_isNeedChanged([](const Integer* first, const Integer* second){return *first < *second;}) {}

	void SetUp()
	{
		fillData();
	}

	void TearDown()
	{
	}

	const Integer _sizeArray;

	const Integer _countIterations;

	std::vector<Integer> _data;

	Random<std::minstd_rand, Integer> _rnd;

	std::vector<Integer*> _dataPointers;

	std::function<bool (const Integer*, const Integer*)> _isNeedChanged;

	void fillData()
	{
		for (Integer i = 0; i < _sizeArray; i++)
		{
			_data[i] = _rnd();
		}
	}

};

TEST(MathTest, checkPowerOfTwoGetter)
{
	EXPECT_EQ(ULONG_MAX, getPowerOfTwo(0));
	EXPECT_EQ(0, getPowerOfTwo(1));

	EXPECT_EQ(8, getPowerOfTwo(500));
	EXPECT_EQ(10, getPowerOfTwo(1024));
	EXPECT_EQ(10, getPowerOfTwo(1025));
	EXPECT_EQ(9, getPowerOfTwo(1023));
}

TEST(MathTest, checkPowerOfTwoSetter)
{
	EXPECT_EQ(1, setPowerOfTwo(0));
	EXPECT_EQ(2, setPowerOfTwo(1));
	EXPECT_EQ(512, setPowerOfTwo(9));
	EXPECT_EQ(1024, setPowerOfTwo(10));
}

TEST_F(DMMathTest, checkHoarSortSegment)
{
	for (Integer j = 0; j < _countIterations; j++)
	{
		fillData();

		std::map<Integer, Integer> countIntegeres;

		for (Integer i = 0; i < _sizeArray ; i++)
		{
			countIntegeres.insert(std::pair<Integer, Integer>(i, 0));
		}

		for (Integer i = 0; i < _sizeArray; i++)
		{
			std::map<Integer, Integer>::iterator item = countIntegeres.find(_data[i]);

			item->second++;
		}

		for (Integer i = 0; i < _sizeArray; i++)
		{
			_dataPointers[i] = &_data[i];
		}

		sortSegment<Integer*, Integer>(_dataPointers, 0, _sizeArray, _isNeedChanged);

		std::map<Integer, Integer> countIntegeresAfterSorting;

		for (Integer i = 0; i < _sizeArray ; i++)
		{
			countIntegeresAfterSorting.insert(std::pair<Integer, Integer>(i, 0));
		}

		for (Integer i = 0; i < _sizeArray - 1; i++)
		{
			ASSERT_TRUE(!_isNeedChanged(_dataPointers[i], _dataPointers[i + 1]));

			std::map<Integer, Integer>::iterator item = countIntegeresAfterSorting.find(*_dataPointers[i]);

			item->second++;
		}

		std::map<Integer, Integer>::iterator item = countIntegeresAfterSorting.find(*_dataPointers[_sizeArray - 1]);

		item->second++;

		std::map<Integer, Integer>::const_iterator sortingItem;

		for (std::map<Integer, Integer>::const_iterator originalItem = countIntegeres.cbegin(); originalItem != countIntegeres.cend(); originalItem++)
		{
			sortingItem = countIntegeresAfterSorting.find(originalItem->first);

			EXPECT_EQ(sortingItem->second, originalItem->second) << " Integer of - " << originalItem->first;
		}
	}
}

TEST_F(DMMathTest, checkRandomGenerator)
{
	std::map<Integer, Integer> countIntegeres;

	for (Integer i = 0; i < _sizeArray ; i++)
	{
		countIntegeres.insert(std::pair<Integer, Integer>(i, 0));
	}

	for (Integer i = 0; i < _sizeArray ; i++)
	{
		std::map<Integer, Integer>::iterator item = countIntegeres.find(_data[i]);

		item->second++;
	}

	double chi_square = 0.0f;

	for (Integer i = 0; i < _sizeArray; i++)
	{
		chi_square += countIntegeres[i] * countIntegeres[i];
	}
	chi_square -= _sizeArray;

	Integer nu = _sizeArray - 1;

	double chi_05 = nu - 1.64f * sqrt(2 * (double)nu) + 2/3.0f * 1.64f * 1.64f - 2/3.0f;
	double chi_95 = nu + 1.64f * sqrt(2 * (double)nu) + 2/3.0f * 1.64f * 1.64f - 2/3.0f;

	ASSERT_TRUE((chi_square > chi_05) && (chi_square < chi_95));
}

TEST_F(DMMathTest, checkHoarSortStep)
{
	for (Integer j = 0; j < _countIterations; j++)
	{
		fillData();

		for (Integer i = 0; i < _sizeArray; i++)
		{
			_dataPointers[i] = &_data[i];
		}

		Integer terminator;

		float imprecision = 0.05f;

		Integer* median;

		hoarSortStep<Integer*, Integer>(_dataPointers, 0, _sizeArray, _isNeedChanged, terminator, median);

		sortSegment<Integer*, Integer>(_dataPointers, 0, _sizeArray, _isNeedChanged);

		Integer leftCriteriaBorder = _sizeArray / 2 - (Integer)(_sizeArray * imprecision);
		Integer rightCriteriaBorder = _sizeArray / 2 + (Integer)(_sizeArray * imprecision);

		bool isWithinTheError = false;

		Integer index = leftCriteriaBorder;
		Integer item = *_dataPointers[index];

		while ((item != *median) && (index <= rightCriteriaBorder))
		{
			index++;
			item = *_dataPointers[index];
		}

		if (index <= rightCriteriaBorder)
			isWithinTheError = true;

		EXPECT_TRUE(isWithinTheError) << "Iteration number - " << j << "; Median - " << *median << "; Item - " << item;
	}
}

int main(int argc, char** argv)
{
	testing::InitGoogleTest(&argc, argv);
	RUN_ALL_TESTS();
	std::getchar(); // keep console window open until Return keystroke
}

